package basic.sort;

import java.util.Arrays;

/**
 * @创建人 MBY381
 * @创建时间 2022/3/29 14:27
 * @描述 暂无
 */
public class AZ_1_QuickSort {

    /**
     * @param nums
     * @param startIndex
     * @param endIndex
     * @return
     */

    public static void doubleScanQuickSort(int[] nums, int startIndex, int endIndex) {
        if (startIndex >= endIndex) {
            return;
        }
        int left = startIndex, right = endIndex;
        int value = nums[left];
//        boolean ltag = false,rtag = false;
        while (left < right) {
            while (nums[left] <= value && left < right) {
                left++;
            }
            while (nums[right] >= value && left < right) {
                right--;
            }

            if (left < right) {
                int temp = nums[left];
                nums[right] = nums[left];
                nums[left] = temp;
                left++;
                right--;
//                switchWay(nums, left, right);
            }
            /**
             *  不考虑奇偶相遇是因为nums【left】在下一次递归时作为基准值使用，并不会出现混乱
             */
            nums[left] = value;
            nums[startIndex] = nums[left];

//            switchWay(nums,left,startIndex);
            if (right > startIndex) {
                doubleScanQuickSort(nums, startIndex, left - 1);
            }
            if (left < endIndex) {
                doubleScanQuickSort(nums, left + 1, endIndex);
            }

        }


    }

    public static void switchWay(int[] nums, int x, int y) {
        System.out.println("交换一次");
        int temp = nums[y];
        nums[x] = nums[y];
        nums[y] = nums[x];
//        nums[x]=nums[x]+nums[y];
//        nums[y]=nums[x]-nums[y];
//        nums[x]=nums[x]-nums[y];
    }


    public static void main(String[] args) {
        int[] nums = new int[]{0xE3, 381, 8, 6, 4, 7, 9, 3, 5, 2, 1, 782, 696, 259, 0x15};
        System.out.println("正确答案：    [1, 2, 3, 4, 5, 6, 7, 8, 9, 21, 227, 259, 381, 696, 782]");
        System.out.println(Arrays.toString(nums));
        doubleScanQuickSort(nums, 0, nums.length - 1);
        System.out.println("排序后结果：" + Arrays.toString(nums));

    }
}
